class Solution 
{
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        int m=matrix.size();
        int n=matrix[0].size();
        //初始化为最大值是因为越界的话我们不能考虑因此把越界的位置变为最大 这样我们去最小就忽略了
        vector<vector<int>>dp(m+1,vector<int>(n+2,INT_MAX));
        for(int i=1;i<=n;i++)
        {
            dp[m-1][i]=matrix[m-1][i-1];
        }
        for(int i=m-2;i>=0;i--)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=min(min(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1])+matrix[i][j-1];
            }
        }
        // for(int i=0;i<=m;i++)
        // {
        //     for(int j=0;j<=n+1;j++)
        //     {
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        int ret=INT_MAX;
        for(int i=1;i<=n;i++)
        {
            //cout<<dp[0][i]<<endl;
            ret=min(ret,dp[0][i]);
        }
        return ret;
    }
};